/*
 * @Author: 缄默
 * @Date: 2021-11-15 20:09:33
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-30 16:14:57
 */

//矩阵的最小路径和


#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

int minSum(vector<vector<int>>& m);

int main() {
    vector<vector<int>> m{
        {1, 3, 5, 9},
        {8, 1, 3, 4},
        {5, 0, 6, 1},
        {8, 8, 4, 0}
    };
    cout << minSum(m) << endl;
    return 0;
}

//动态规划实现最小路径和
int minSum(vector<vector<int>>& m) {
    vector<int> arr(m[0].size(), m[0][0]);

    //算出横向路径长度
    for (int i = 1; i < arr.size(); i++) {
        arr[i] = arr[i - 1] + m[0][i];
    }

    //每一列都进行计算
    for (int i = 1; i < m.size(); i++) {
        arr[0] = m[i][0] + arr[0];

        //计算每一行的变量
        for (int j = 1; j < arr.size(); j++) {
            //压缩空间 将空间复杂度从O（mn)压缩到O(n)
            arr[j] = min(arr[j - 1], arr[j]) + m[i][j];
        }
    }
    return arr[arr.size() -  1];
}
